package 树与图.字典树.二叉树;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 102.二叉树的层序遍历
 *
 * 解题思路： 层序遍历，每一层遍历完后，将队列（先进先出）中的元素出队，然后将出队元素的孩子节点压入队列
 *
 * 步骤：1、初始化队列：首先，创建一个队列，用于存放待遍历的的节点
 *      2：根节点入队：将二叉树的根节点入队，如果根节点为空，则直接返回空的列表
 *      3：遍历队列，只要队列不为空，则进行如下操作：
 *        - 将当前出队列的节点依次出队，并访问这些节点
 *        - 将出队节点的这些孩子节点依次入队列

 * @Author lf
 * @Date 3/27/2024
 */
public class LevelOrderTraversal {

    // 实现二叉树的层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        // 如果根节点为空，则直接返回空的列表
        if(root == null){
            return result;
        }
        // 创建队列
        Queue<TreeNode> queue = new LinkedList<>();
        // 根节点入队列
        queue.add(root);
        // 只要队列不为空，就可以进行遍历
        while (!queue.isEmpty()){
            // 当前层的遍历结果存放数组
            List<Integer> currentLevel = new ArrayList<>();
            // 当前层的节点元素个数
            int currentLevelSize = queue.size();
            for (int i = 0; i < currentLevelSize; i++) {
                // 节点出队列，孩子节点入队列
                TreeNode curentNode = queue.poll();
                currentLevel.add(curentNode.val);
                // 添加孩子节点
                if(curentNode.left != null){
                    queue.add(curentNode.left);
                }
                if(curentNode.right != null){
                    queue.add(curentNode.right);
                }
            }
            // 层级放到结果中
            result.add(currentLevel);
        }
        return result;
    }

    public static void main(String[] args) {
        // 示例二叉树的构建
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        LevelOrderTraversal solution = new LevelOrderTraversal();
        List<List<Integer>> result = solution.levelOrder(root);

        // 打印结果
        for (List<Integer> level : result) {
            System.out.println(level);
        }
    }

    // 定义二叉树的节点结构
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
